package Tree;

import com.sun.org.apache.xpath.internal.operations.Bool;

/**
 * @author yyq
 * @create 2021-10-27 13:16
 * 这里我们手动构建二叉树
 * 实现二叉树的前序中序后序遍历
 * 借用之前实现二叉树的遍历
 * 来实现线索化二叉树
 *
 */
public class ThreadedBinaryTree {

    public static TreeNode pre=null;

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.right=new TreeNode(6);
        root.left.left=new TreeNode(4);
        root.right.left=new TreeNode(5);
        inFixOrder(root);
        threadList(root);

    }


    //中序遍历 -线索化二叉树
    public static void inFixOrder(TreeNode root){
        if(root.left!=null) inFixOrder(root.left);

        System.out.println("线索化----"+root.data);
        threadNode(root);


        if(root.right!=null) inFixOrder(root.right);
    }


    //线索化二叉树
    public static  void  threadNode(TreeNode root){
        if(root==null) return;
        if(root!=null){
            //设置root的左子树
            // 举例中序遍历的第一个元素  这里为 4  pre=null root->4
            if(root.left==null&&pre!=null) {
                root.left=pre;
                root.leftType=1;
            }
            //设置pre的右子树 pre的右子树为空
            if(pre!=null&&root!=null&&pre.right==null) {
                pre.right=root;
                pre.rightType=1;
            }
            //important
            pre=root;
        }
    }

    //中序遍历线索二叉树 -关键找到第一个节点
    public static void threadList(TreeNode temp){
        TreeNode root=temp;
        while(true){
            //step 1 找到左子树的第一个节点 左下角
            if (root==null) break;

            while(true){
                // 必须加上root.lefttype=1哦 否则你不知道 他的left到底是pre节点还是子节点
                if(root.left==null||root.leftType==1) break;
                root=root.left;
            }
            System.out.println(root.data);
            //step 2 遍历直到没有 right不指向后续节点
            while(root.rightType==1){
                root=root.right;
                System.out.println(root.data);
            }
            //step 3 指向右边
            // System.out.println(root.data);
            root=root.right;
            continue;
        }
    }

}
